P2895 (USACO08FEB) Meteor Shower S

题目描述

贝茜听说一场特别的流星雨即将到来：这些流星会撞向地球，并摧毁它们所撞击的任何东西。她为自己的安全感到焦虑，发誓要找到一个安全的地方（一个永远不会被流星摧毁的地方）。

如果将牧场放入一个直角坐标系中，贝茜现在的位置是原点，并且，贝茜不能踏上一块被流星砸过的土地。

根据预报，一共有 $M$ 颗流星 $(1 \leq M \leq 50, 000)$ 会坠落在农场上，其中第 $i$ 颗流星会在时刻 $T_{i}$ （ $0 \leq T_{i} \leq 1000$ ）砸在坐标为 $(X_{i}, Y_{i}) (0 \leq X_{i} \leq 300$ ， $0 \leq Y_{i} \leq 300)$ 的格子里。流星的力量会将它所在的格子，以及周围 $4$ 个相邻的格子都化为焦土，当然贝茜也无法再在这些格子上行走。

贝茜在时刻 $0$ 开始行动，她只能在会在横纵坐标 $X, Y \geq 0$ 的区域中，平行于坐标轴行动，每 $1$ 个时刻中，她能移动到相邻的（一般是 $4$ 个）格子中的任意一个，当然目标格子要没有被烧焦才行。如果一个格子在时刻 $t$ 被流星撞击或烧焦，那么贝茜只能在 $t$ 之前的时刻在这个格子里出现。贝茜一开始在 $(0, 0)$ 。

请你计算一下，贝茜最少需要多少时间才能到达一个安全的格子。如果不可能到达输出 $- 1$ 。

输入格式

共 $M + 1$ 行，第 $1$ 行输入一个整数 $M$ ，接下来的 $M$ 行每行输入三个整数分别为 $X_{i}, Y_{i}, T_{i}$ 。

输出格式

贝茜到达安全地点所需的最短时间，如果不可能，则为 $- 1$ 。

样例 1

样例输入

样例输出

代码

#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

  

int m;

int ans[305][305], death[305][305];//记录答案和死亡时间

struct coord {int x, y;};

queue<coord> Q; //记录状态

const int walk[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

  

void update(int a, int b, int t) {

    if (a >= 0 && a < 305 && b >= 0 && b < 305)  // 边界检查

        death[a][b] = min(death[a][b], t);

}

  

int main() {

    //数据初始化并记录地块最早失效时间

    cin >> m;

    memset(death, 0x3f, sizeof(death));

    memset(ans, -1, sizeof(ans));

    for (int i = 0; i < m; i++) {

        int x, y, t;

        scanf("%d%d%d", &x, &y, &t);

        update(x, y, t);

        for (int i = 0; i < 4; i++) {

            int p = x + walk[i][0];

            int q = y + walk[i][1];

            update(p, q, t);}

    }

    //队列初始化

    Q.push((coord){0, 0});

    ans[0][0] = 0;

    while (!Q.empty()) {

        coord u = Q.front();

        int ux = u.x, uy = u.y;

        if (death[ux][uy] > 1000) {

            cout << ans[ux][uy];

            return 0;

        } //如果安全就结束

        Q.pop();

        for (int i = 0; i < 4; i++) {

            int x = ux + walk[i][0], y = uy + walk[i][1];

            if (0 <= x && x < 305 && 0 <= y && y < 305 && ans[x][y] == -1 && ans[ux][uy] + 1 < death[x][y]) {

                ans[x][y] = ans[ux][uy] + 1;

                Q.push((coord){x, y});

            }
        }
    }

    cout << -1;

}

思路

广度优先搜索，注意边界条件